sort.task <- c() 


#metoda generująca graf dla probleu sortowania ciągu liczb
sort.generateGraph <- function(startSequence){
	graph=newGraph.createGraph()
	if(sort.cost(startSequence)==0)
		isEndNode=TRUE
	else 
		isEndNode=FALSE
	graph$addNode(sort.seqToName(startSequence),startSequence,NULL,0,sort.cost(startSequence),TRUE,isEndNode)
	graph=sort.generateNeighbours(graph,startSequence)
	return(graph)
}

#zamienia wektor na ciąg znaków łącząc poszczególne elementy znakiem '|'
sort.seqToName<-function(sequence){
	return(paste(sequence, collapse="|"))
}

#metoda generująca wszystkich sąsiadów podanej sekwencji
sort.generateNeighbours<- function(graph,sequence){
	nodeName=sort.seqToName(sequence)
	generatedSequences=sort.generate(list(sequence))	
	addedSequences=list()
	for(i in 1:length(generatedSequences)){	
		generatedName=sort.seqToName(generatedSequences[[i]])
		if(is.null(graph$getNode(generatedName))){
			if(sort.cost(generatedSequences[[i]])==0)
				isEndNode=TRUE
			else 
				isEndNode=FALSE
			graph$addNode(generatedName,generatedSequences[[i]],nodeName,1,sort.cost(generatedSequences[[i]]),FALSE,isEndNode)
			addedSequences[length(addedSequences)+1]=generatedSequences[i]
		}
		else{
			graph$connect(generatedName,nodeName,cost=1)
		}
	}
	if(length(addedSequences)>0){
		for(i in 1:length(addedSequences)){
			graph=sort.generateNeighbours(graph,addedSequences[[i]])
		}
	}
	return(graph)
}

#generuje sekwencje które można uzyskać z podanej sekwencji liczb
sort.generate <- function(XS){
	res<-list()
	
	for(i in 1:length(XS)){
		x<-XS[[i]]
		
		for(j in 1:(length(x)-1)){
			for(k in (j+1):length(x)){
				res[[length(res)+1]] <- sort.swap(x,j,k)
			}
		}
	}	
	
	return(res)
}

sort.swap <- function(x,i,j){
	xn<-x
	xn[i]<-x[j]
	xn[j]<-x[i]
	
	return(xn)
}


sort.cost <- function(s){
	## s <- sort.task[x]
	len <- length(s)
	
	q = 0
	
	for(i in 1:len){
		for(j in i:len){
			if(s[i]>s[j]){
				q = q + 1
			}
		}
	}
	
	return(q)
}

